package leetcode_数组.leetcode_前缀和数组;

import java.util.Arrays;

/**
 * 除自身以外数组的乘积
 * 算法 :
 * 除这个元素之外的乘积就是这个元素左边元素的总乘积 × 右边元素的总乘积
 * 定义两个数组 l r , l数组存储元素左边的总乘积 , r数组存储元素右边的总乘积
 * r[i] 表示第 i 个元素前所有元素的乘积 , 没有则为 1
 * l[i] 同上
 */
public class _238 {
    public static void main(String[] args) {
        int[] ints = {1, 2, 3, 4};
        System.out.println(Arrays.toString(productExceptSelf(ints)));
    }

    public static int[] productExceptSelf(int[] nums) {
        int[] l = new int[nums.length], r = new int[nums.length];
        l[0] = 1;
        r[nums.length - 1] = 1;
        for (int i = 1; i < nums.length; i++) {
            l[i] = l[i - 1] * nums[i - 1];
        }
        for (int i = nums.length - 2; i >= 0; i--) {
            r[i] = r[i + 1] * nums[i + 1];
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = l[i] * r[i];
        }
        return nums;
    }
}
